package com.chj.dfs.class04;

import java.util.ArrayDeque;
import java.util.Deque;

public class Code15_NumberOfIslands {

	public static class Node {
		public int x;
		public int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void DFS(int[][] mark, char[][] grid, int x, int y) {
		// 标记访问过的节点
		mark[x][y] = 1;
		// 说明这种常量只声明一次
		int dx[] = { -1, 1, 0, 0 };
		int dy[] = { 0, 0, -1, 1 };
		for (int i = 0; i < 4; i++) {
			int newx = dx[i] + x;
			int newy = dy[i] + y;
			if (newx < 0 || newx >= mark.length || newy < 0 || newy >= mark[newx].length) {
				continue;
			}
			if (mark[newx][newy] == 0 && grid[newx][newy] == '1') {
				DFS(mark, grid, newx, newy);
			}
		}
	}

	public static void BFS(int[][] mark, char[][] grid, int x, int y) {
		int dx[] = { -1, 1, 0, 0 };
		int dy[] = { 0, 0, -1, 1 };

		Deque<Node> queueNode = new ArrayDeque<Node>();
		Node root = new Node(x, y);
		queueNode.addLast(root);

		mark[x][y] = 1;
		while (!queueNode.isEmpty()) {
			Node frontNode = queueNode.pollFirst();
			x = frontNode.x;
			y = frontNode.y;

			// 扩展四个方向
			for (int i = 0; i < 4; i++) {
				int newx = dx[i] + x;
				int newy = dy[i] + y;
				// 确保被考虑的点在底图内
				if (newx < 0 || newx >= mark.length || newy < 0 || newy >= mark[newx].length) {
					continue;
				}
				if (mark[newx][newy] == 0 && grid[newx][newy] == '1') {
					// 新位置入队
					Node node = new Node(newx, newy);
					queueNode.addLast(node);
					mark[newx][newy] = 1;
				}
			}
		}
	}

	public static int numIslands(char[][] grid) {
		if (grid == null || grid.length == 0)
			return 0;
		int island_num = 0;
		// 初始化mark数组
		int[][] mark = new int[grid.length][grid[0].length];

		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				if (mark[i][j] == 0 && grid[i][j] == '1') {
					BFS(mark, grid, i, j);
//					DFS(mark, grid, i, j);
					island_num++;
				}
			}
		}
		return island_num;
	}

	public static void main(String[] args) {
		char[][] grid1 = { { '1', '1', '1', '1', '0' }, { '1', '1', '0', '1', '0' }, { '1', '1', '0', '0', '0' },
				{ '0', '0', '0', '0', '0' } };
		int numIslands1 = numIslands(grid1);
		System.out.println(numIslands1);

		char[][] grid2 = { { '1', '1', '0', '0', '0' }, { '1', '1', '0', '0', '0' }, { '0', '0', '1', '0', '0' },
				{ '0', '0', '0', '1', '1' } };
		int numIslands2 = numIslands(grid2);
		System.out.println(numIslands2);
	}
}
